package com.mc.algorithm;


public class ThirtySix {
	private static int[] copy;
	public static void revPair(int [] a){
		copy = new int[a.length];
		for(int i=0;i<a.length;i++)
			copy[i] = a[i];
		int res = divide(a, 0, a.length);
		System.out.println(res);
	}
	public static int divide(int[] a, int low, int high){
		if(low==high){
			copy[low]=a[low];
			return 0;
		}
		int mid = low+(high-low)/2;
		int left =divide(a,low,mid);
		int right =divide(a,mid+1,high);
		int head = low;
		int tail = high;
		int count = 0;
		int cpindex = high;
		while(head>=low&&tail>=mid+1){
			if(a[head]>a[tail]){
				copy[cpindex--] = a[head--];
				count+=tail-mid;
			}
			else{
				copy[cpindex--] = a[tail--];
			}
		}
		for(;head>=low;head--)
			copy[cpindex--]=a[head];
		for(;tail>=mid+1;tail--)
			copy[cpindex--]=a[tail];
		return left+right+count;
	}
	public static void main(String[] args) {
		ThirtySix.revPair(new int[]{7,5,6,4});
	}
}
